In a digital system, information is represented in a form of a binary sequence of ‘0’ or ‘1,’ and a plurality of binary sequences creates a meaningful information set. The meaningful information set is created in units of 8 bits, 16 bits or 32 bits according to the register size of a main processor. The unit bit is differently referred to as a word. In the information theory, the information, which consists of the information sets or is created in units of words, is referred to as an information source.
Each word constituting the information source is referred to as a symbol. Each symbol has different probability of occurrence. Once the probability of occurrence of each symbol is determined, entropy can be defined. The entropy indicates the amount of information to be stored or transferred according to Shannon's theory. If there is n symbols and the probability of occurrence of an ith symbol is pi, the entropy can be defined as the following formula 1.
                    H        =                              ∑                          i              =              1                        n                    ⁢                                          ⁢                                    P              i                        ⁢            log            ⁢                                                  ⁢            2            ⁢                          1                              P                i                                                                        [                  Formula          ⁢                                          ⁢          1                ]            
The entropy shows not only an average information amount per symbol but also a minimum code-length of an information source when the information source is coded. As such, the method of coding the code-length of the information source close to the entropy by using the statistical properties of symbols is referred to as entropy coding.
The entropy coding method is suggested in various ways in order to have the minimum bit number per symbol. The representative conventional entropy coding methods include a run length coding (RLC) method, a Hoffman coding and an arithmetic coding method.
The RLC method is to represent a repeated pixel block as one representative value and the repeated number of the representative value by using the fact that the sequences statistically have similar or identical values. For example, in integer data set {7, 3, 0, 0, 0, 0, 0, 0, 0} to be compressed, ‘0’ is repeated 7 times. Accordingly, if the repeated information ‘0’ is the representative value and the flag showing the repeated number is represented as n, the integer data set {7, 3, 0, 0, 0, 0, 0, 0, 0} is coded to be {7 3 0 N 7}. As a result, the symbols having the whole 9 byte size can be coded to be data having the 5 byte size.
Next, the Hoffman coding method is to change a constant length sign to a variable length sign. In particular, the Hoffman coding method is reduce an average sign length rather than an original sign length by allowing a short sign to be assigned to the symbol having a high generation frequency and a long sign to be the symbol having a low generation frequency. For example, an English text represented by an ASCII code employs 7 bits per letter. However, if the Hoffman coding method is applied, the English letter is represented by using the sign length of 7 bits or less on the average by allowing the letter having the high generation frequency such as “e” and “s” and to be represented with symbols of 7 bits or less and special signs having the low generation frequency to be represented with symbols of 7 bits or more.
Finally, the arithmetic coding method is to represent a variable length symbol string in which various symbols are bound as one constant length sign. The various symbols are bound such that the probability of occurrence of the symbol string can be nearly regular. In the arithmetic coding method, an input symbol is defined in a real number section between 0 and 1. The longer symbols show their narrower intervals. The bit number indicates the size of the interval. The increased number of symbols results in the smaller number of sections used to represent the symbols and the increased number of information bits for indicating the sections.
As described above, in the digital system, the computation is performed in units of words. The units of words are sets having 8 bits, 16 bits or 32 bits. As such, all numbers and letters have been represented based on units of bits. Since this conventional representing method needs more bits than bits necessary to transmit and store meaningful information, the data compression is requested for effective transmission and storage.
Typically, when a video signal including a series of video “frame” is represented in a digital form, a considerable amount of transmitted data is generated. However, since the usable frequency band width of the typical transmission channel is limited, the compression of transmission data is needed in order to transmit the considerable amount of digital data.
However, in accordance with the conventional method of compressing data or coding/decoding entropy, increasing the compression rate results in raising the complexity of the coding device or the decoding device due to their properties.
Also, the conventional method of compressing data or coding/decoding entropy brings about the time delay according to the high compression rate.